package com.datastructures.sort;

/**
 * @author MaoLin Wang
 * @date 2019/10/2816:55
 */
public class InsertSort {
    public static void main(String[] args) {

        int[] array =new int[100000];
        for (int i=0;i<100000;i++){
            array[i]=(int)(Math.random()*100000);
        }

        long begintime=System.currentTimeMillis();
        System.out.println("开始时间"+begintime);

        insertSort(array);
        long endtime=System.currentTimeMillis();
        System.out.println("结束时间"+endtime);
        System.out.println("用时："+(endtime-begintime)+"ms");
        int[] arr= {213,43,22,11,324,11,4};

    }

    public static void insertSort(int[] arr){

        for (int i=1;i<arr.length;i++){
            //待插入数据
            int insertVal=arr[i];
            //待插入位置下标
            int insertIndex=i-1;

            /**
             * 如果待插入下标小于零，说明待插入数据最小，应放在第一个位置
             * 如果待插入值大于arr[inserIndex]，则停止循环，说明待插入值在有序表中是最大的，应插入到当前insertIndex后一个位置
             */
            while (insertIndex>=0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            //判断是否需要赋值
            if (insertIndex+1 != i){
                arr[insertIndex+1]=insertVal;

            }

          //  System.out.println("第"+i+"次排序结果：");
          //  System.out.println(Arrays.toString(arr));

        }
    }
}
